Abstract

In this paper, a new approach that applies the concept of the Analytic Hierarchy Process (AHP) in the area of routing in communication networks is proposed. AHP is a well-known model in the area of decision making with multiple objectives. In addition, a new algorithm called Enhanced Best Effort Quality of Service Routing (QoS) with Multiple Prioritised Metrics is proposed for connection-oriented point-to-point communications. Four QoS metrics have been considered: delay, bandwidth, security and loss probability. The results presented and discussed in this paper are focussed on demonstrating the effects of metric prioritisation on the routing decisions. It is found that changing priority of a metric from 0 (the lowest priority) to 1 (the highest priority) applying the proposed algorithm improves the value of that metric by an average of (20–60)% for 90% of utilisation range.

Keywords: Quality of Service (QoS) routing; Analytic hierarchy process (AHP); Computer networks; Security

Article Outline

1. Introduction

2. The analytic hierarchy process (AHP)

2.1. Applying AHP in best effort QoS routing: an illustrative example

2.1.1. Part 1 (metric weightings)

2.1.2. Part 2 (priority weightings)

2.1.3. Part 3 (Total score calculations)

2.2. EBQRMPM without prioritisation

3. Simulation and experimental design

3.1. Network model

3.2. Link metrics

3.2.1. Delay

3.2.2. Residual bandwidth

3.2.3. Security

3.2.4. Loss probability

3.3. Evaluation method

4. Performance evaluations and results analysis

4.1. Effect of changing priorities

4.1.1. Effect of changing priorities for delay

4.1.2. Effect of changing priorities for bandwidth

4.1.3. Effect of changing priorities for vulnerability

4.1.4. Effect of changing priorities for loss probability

5. Limitations of EBQRMPM

6. Conclusions and future work

References

1. Introduction

Recent advances in high speed networking technology have created opportunities for the development of multimedia applications that are characterised by multiple quality of service (QoS) requirements. One of the key issues in supporting QoS traffic is QoS routing.

There are two types of routing: constrained and best effort. The proposed algorithm is for best effort but with some enhancements that help to deal with multiple metrics.

The Internet provides a best effort service to applications and thus cannot guarantee to meet the QoS requirements of multimedia communications. However, research and development efforts have been made towards providing QoS guarantees in the Internet. In [1], a new bandwidth allocation mechanism (BAM) is proposed. It uses less bandwidth than the peak rate BAM, while providing the same service. In [2], the use of QoS routing to enhance the support of IP Telephony is proposed. The proposed scheme is based on QoS intradomain OSPF routing, an extension of the conventional OSPF. Refs. [3] and [4] present a good overview of QoS in the Internet. The Internet Engineering Task Force (IETF) has proposed many service models, mechanisms and frameworks to meet the demand for QoS. Among them are Resource Reservation Protocol (RSVP) [5], Integrated Services (IntServ) [6], Differentiated Services (DiffServ) [7], Multiprotocol Label Switching (MPLS) [8] and A Framework for QoS-based Routing in the Internet [9].

Although we generally state that QoS should be guaranteed, in practice the user should be able to specify the degree (or level) of guarantees. In general, there are three levels of guarantee [4] and [10]: Hard or deterministic guarantee, Soft or statistical guarantee and Best effort. In some cases, one connection may use different levels of guarantee for different QoS parameters.

Various approaches have been considered to deal with QoS characterisation. Namely, by using a single metric, a single compound metric or multiple metrics [11], [12] and [13].

The main objectives of this paper are: firstly, to propose a new approach that applies the concept of the Analytic Hierarchy Process (AHP) [14] and [15] in the area of routing in communication networks. Secondly, we propose an algorithm that supports metric prioritisation in best effort QoS routing. Thirdly, more detailed results are discussed and analysed to demonstrate effects of metric prioritisation on the performance of the proposed algorithm.

2. The analytic hierarchy process (AHP)

The AHP, a multi-criteria technique developed by Saaty [14] and [15], is a robust and flexible multi-criteria decision analysis methodology. Although most applications of AHP are in the area of socio-economic planning, there have been some applications in decisions related to road networks [16], petroleum pipeline networks [17], Health service [18], project management [19] and telecommunications [12], [20], [21], [22] and [23].

In general, there are four basic steps in using AHP [21] and [22]:

1. The description of a complex decision problem as a hierarchy.

2. The use of pair-wise comparisons to estimate the relative weight (importance or priority) of the various elements to each other. This gives what is called the priority weights.

3. The use of pair-wise comparisons to estimate the relative weight (importance) of the various elements on each level of the hierarchy. This gives what is called the score of each level in each element.

4. The integration of these weights, from 2 and 3, to develop an overall score of decision alternatives. Then, the alternative with maximum overall score will be selected.

2.1. Applying AHP in best effort QoS routing: an illustrative example

In this section, an example of a small network is presented in order to illustrate the proposed algorithm that introduces metrics prioritisation applying the concept of AHP in the area of QoS routing. It is called Enhanced best effort QoS routing with multiple prioritised metrics (EBQRMPM). It is proposed for connection-oriented point-to-point communications. The basic principles of applying AHP in QoS routing are discussed in [12] and [23].

Changing priority is a natural action in order to meet some special requirements for some traffic. For example, when routing delay sensitive traffic as in real-time applications, the delay metric will be the first priority while the loss metric will be in a lower priority level if not the least. In contrast, when routing loss sensitive traffic as in data transfer applications, the loss metric will be the first priority while the delay metric will be in a lower priority level.

Consider the network (N) shown in Fig. 1. It consists of 6 nodes and 8 links. Therefore, its average degree is 2.7, (2×8/6). Each link has four metrics; Residual bandwidth (b), loss probability (l), delay (d) and security (s), (1: secure, 0: insecure).

Fig. 1. Example of a small network.

It is required to set up a connection between two nodes s and t. It is better to consider all the four QoS metrics. On top of that, priorities of the metrics have to be considered when making the routing decision. For this example, the priority order is bandwidth (1), loss probability (2), delay (3) and security (4).

In general, there are three main parts of applying AHP: 1—metric weightings, 2—priority weighting and 3—total score calculations. As will be seen shortly, the first and the second parts have very similar steps, using pair-wise comparisons. Therefore, one step will be explained in detail and the final results of the others are given.

2.1.1. Part 1 (metric weightings)

Step-A: Find all possible paths between two given nodes (s,t). This step includes finding the overall metrics of each path.

As can be seen from Fig. 1, there are seven paths from (s) to (t). These seven paths are summarised in Table 1 and as can be seen from the table, each path consists of more than one link. Now assume that the overall metrics of each path are given as shown in Table 2.

Table 1.

The seven paths from (s) to (t)

Path #	1	2	3	4	5	6	7
Links	s12t	s1234t	s132t	s134t	s34t	s32t	s312t

Table 2.

Paths metrics: b (res. Bandwidth), l (loss), d (delay) and s (security)

Path no#	Metrics
	b	l	d	s
1	20	3e-6	20	1
2	15	5e-6	4	0
3	40	20e-6	3	1
4	80	10e-6	10	0
5	90	8e-6	5	1
6	100	15e-6	13	1
7	110	13e-6	15	1

Step-B: Generate path–path pair-wise comparison matrix (ppcm) of each metric.

This step determines how well each path “scores” on each metric comparing to the all other paths. To determine these scores, EBQRMPM constructs, for each metric, a pair-wise comparison matrix with size of (P×P), where P is the number of paths. It is called path–path pair-wise comparison matrix for a given metric (ppcm(metric name)). The basic idea of this matrix is to compare a metric i, bandwidth (b) for example, of a path j to the bandwidth of the all other paths. i.e. to calculate

.

In order to calculate the elements of this matrix, it has been found that it is necessary to define a parameter, criterion, of each metric. We consider this as part of our modifications on AHP. Three criteria are defined:

• Min: to represent all metrics that are to be minimised. For example, delay, loss probability, cost, vulnerability and number of hops.

• Max: to represent all metrics that are to be maximised. For example, bandwidth.

• Bin: to represent all metrics that have a binary nature. For example, security (1=secured, 0=unsecured). We made this assumption for security in particular to show how the proposed algorithm could deal with any number and type of metrics. However, security has not been defined as a QoS metric in current routing algorithms, to the best of our knowledge. Nevertheless, it is worth mentioning that in this illustrative example, security is considered as a binary case but in a coming section, Section 4, security is considered as a range [0,1] and the use of vulnerability concept is introduced and more details are discussed there.

It is common sense that comparing a metric of a path to itself has no preference, weight = 1. Moreover, comparing a metric of path j to path i will be the reciprocal of path i to path j. these two comments can expressed as the following equations:

ppcm(i,i)=1

(1)

ppcm(j,i)=1/ppcm(i,j).

(2)

Since the original AHP comes from social environments, relative weights between metrics are generated based on the personal feeling of a customer, i.e. how important is metric i relative to metric j? However, in computing and engineering, most of parameters are quantitative. Therefore, other modifications are proposed in order to reflect relative importance between metrics of different paths based on their real values. It is found that these modifications depend on the criteria of metrics (min, max or bin). It is proposed to use the following equations for metrics that are to be maximised or minimised:

(3)

(4)

Regarding security when considered as a binary metric, it is found that some sort of approximation is needed in order to avoid division by zero in some cases and to come up with values that can reflect the security importance of a path relative to another path. For example, 1 if both are secured or unsecured or 2 when comparing a secured path to unsecured one. This can be achieved by applying the following equations:

(5)

Taking bandwidth as an example, the path–path pair-wise comparison matrix will be as follows:

Thus, for example, with respect to bandwidth path 1 and path 4 (b1=20:b4=80), path 1 is 4 times smaller (bad) than path 4, or path 1 has a weight of 0.25 relative to path 4. Alternatively, path 4 is 4 times better than path 1.

Step-C: Generate normalised path–path pair-wise comparison matrix of each metric.

For each of ppcms columns, divide each entry in column j of ppcm by the sum of the entries in the same column [15]. This yields a new normalised matrix (call it nppcm) in which the sum of the entries in each column is 1. This can be expressed as follows:

(6)

Therefore, for the path–path pair-wise comparison matrix ppcm, Step_B yields

Step-D: Generate average normalised path–path pair-wise comparison matrix of each metric.

This can be calculated by finding the average of the entries in row i of nppcm [15]. This can be expressed as follows:

(7)

The size of the anppcm matrix is [n×P] where n is the number of metrics and P is the number of paths as mentioned earlier. The anppcm for bandwidth is shown as follows:

Repeating step-B to step-D for the other three metrics considering metrics with min and bin criteria, the anppcm for all metrics is given in Table 3:

Table 3.

Average normalised path scores on each metric (anppcm(n×P))

Path #	P1	P2	P3	P4	P5	P6	P7	∑
Metrics
bandwidth	0.0439	0.0329	0.0879	0.1758	0.1978	0.2198	0.2418	1
Loss	0.3502	0.2101	0.0525	0.1051	0.1313	0.0701	0.0809	1
Delay	0.0464	0.2321	0.3095	0.0929	0.1857	0.0714	0.0619	1
security	0.2	0	0.2	0	0.2	0.2	0.2	1

2.1.2. Part 2 (priority weightings)

Step-E: Generate average normalised priority pair wise comparison matrix.

In the original AHP, each metric has to be given absolute numbers that reflect the relative importance of that metric comparing to the other metrics based on a customer's feeling. Then, the same previous steps (B–D) is repeated in order to find what is called average normalised priority pair-wise comparison matrix, anprpcm (n), where n is the number of metrics. However, one of the proposed modifications on AHP is to assume that the metrics are given weights directly but in the range [0,1] where the sum of all weights equals one as shown in Table 4.

Table 4.

Average normalised priority weight (with prioritisation: EBQRMPM)

Priority no#	1	2	3	4	∑
anprcm	0.47	0.28	0.16	0.09	1

2.1.3. Part 3 (Total score calculations)

Step-F: Select the required priority of metrics, if there is more than one priority set.

For this example, the priority set will be 0.47, 0.28, 0.16 and 0.09 for Bandwidth, Loss, Delay and Security (BLDS), respectively.

Step-G: Find the total score of each path based on step-E and step-F.

This can be calculated by using the following equation [15]:

(8)

For example, the total score of path 1 can be calculated as follows:

Path 1 total score=0.47×0.0439+0.28×0.3502+0.16×0.0464+0.09×0.2=0.144 which can be seen in Table 5, cell (BLDS, P1). The total scores of the other paths are shown in the first row of the table.

Table 5.

Effect of changing priority on the final path decision applying EBQRMPM algorithm

Priorities order	Total normalised path score							Selected path
	P1	P2	P3	P4	P5	P6	P7
B L D S	0.1441	0.1109	0.1246	0.1259	0.1776	0.1525	0.1642	5
B L S D	0.1542	0.0959	0.1174	0.1199	0.1786	0.1609	0.1732	5
B D L S	0.1089	0.1135	0.1544	0.1246	0.1839	0.1526	0.1619	5
B D S L	0.0992	0.0999	0.1639	0.1177	0.1884	0.1611	0.1697	5
B S L D	0.1368	0.0715	0.1345	0.1077	0.1865	0.1759	0.1870	7
B S D L	0.1169	0.0729	0.1513	0.1069	0.1901	0.1760	0.1858	5
L B D S	0.2019	0.1444	0.1179	0.1126	0.1651	0.1242	0.1338	1
L B S D	0.2119	0.1293	0.11075	0.1066	0.1661	0.1326	0.1428	1
L D B S	0.2023	0.1675	0.1436	0.1029	0.1637	0.1071	0.1129	1
L D S B	0.2121	0.1654	0.1509	0.915	0.1638	0.1057	0.1102	1
L S D B	0.2301	0.1384	0.1382	0.0808	0.1655	0.1206	0.1262	1
L S B D	0.2301	0.1255	0.1238	0.0862	0.1663	0.13.3	0.1379	1
D L B S	0.1449	0.1717	0.1921	0.1007	0.1739	0.1073	0.1094	3
D L S B	0.1551	0.1695	0.1991	0.0892	0.1741	0.1059	0.1067	3
D B L S	0.1094	0.1511	0.1962	0.1089	0.1817	0.1247	0.1281	3
D B S L	0.0996	0.1374	0.2061	0.1021	0.1860	0.1331	0.1358	3
D S B L	0.1174	0.1336	0.2188	0.0817	0.1864	0.1308	0.1309	3
D S L B	0.1379	0.1451	0.2165	0.0771	0.1821	0.1211	0.1205	3
S B L D	0.1662	0.0653	0.1557	0.0746	0.1869	0.1722	0.1791	5
S B D L	0.1464	0.0667	0.1724	0.0738	0.1905	0.1723	0.1771	5
S D B L	0.1467	0.0898	0.1981	0.0641	0.1891	0.1551	0.1571	3
S D L B	0.1667	0.1013	0.1958	0.0595	0.1848	0.1453	0.1465	3
S L B D	0.2017	0.0858	0.1516	0.0663	0.1792	0.1548	0.1604	1
S L D B	0.2034	0.0988	0.1660	0.0609	0.1785	0.1452	0.1487	1

Step-H : Select the path with the maximum total score as the communication path between the two nodes (s,t).

As can be seen from Table 5 , path 5 has the maximum score (0.1776). Consequently, the EBQRMPM algorithm selects path 5 to be the communication path between s and t for this priority set.

Step-I (if another priority set is required): go to Step-E.

Since there are 4 metrics, 24 possible cases of different sets, factorial of 4 (4!), can be generated. They are presented in the first column of Table 5. The achieved total score and selected path for each priority set are shown in the Tables 5 and 6.

For example, consider the priority order shown in the last row of Table 5 (SLDB). It indicates that security is in the first priority that has a weight of 0.47, loss is in the second priority (0.28), delay is in the third priority (0.16) and bandwidth is in the fourth priority (0.09).

Repeating Eq. (8) in order to calculate the total score of path 1 for this priority order gives the following:

Path 1 total score for (SLDB)=0.09×0.0439+0.28×0.3502+0.16×0.0464+0.47×0.2=0.2034 which can be seen in Table 5, cell (SLDB, P1).

As can be seen from Table 5 , for this priority order (SLDB), path 1 has the maximum score (0.2034). Consequently, the EBQRMPM algorithm selects path 1 to be the communication path between s and t for this priority set.

This illustrates clearly how the proposed algorithm, EBQRMPM, changes the selected path from path 5 to path 1 when priority order has been changed from BLDS to SLDB.

As can be seen, if priority of the metrics is changed, the final path decision may change depending on how the total score will be after recalculations. Moreover, Table 6 compares EBQRMPM algorithm, dark cells, with a modified version in which prioritisation of metrics is disabled which will be discussed in the following subsection.

2.2. EBQRMPM without prioritisation

For the sake of comparison, the EBQRMPM algorithm is modified in order to disable the metric prioritisation, i.e. all metrics have the same level of importance or priority. The modified algorithm is called EBQRMM, Quality of Service Routing with Multiple Metrics. There are two possibilities in order to disable prioritisation; firstly, to remove the part of EBQRMPM algorithm that deals with the priority weighting. Secondly, to assign the same priority for all metrics, priority 1. Although, final results of both approaches are the same, it is decided to choose the second approach because it needs less modification than the first one. Clearly, the normalised priority weights for all priorities will be 1/n as can be seen from Table 7, where n is the number of metrics.

The Normalised path scores on each metric will be exactly the same as EBQRMPM (Table 3).

As can be seen from Table 6, Table 7 and Table 8 changing priorities has no effect on the total scores of the paths and consequently has no effect on the final path decision when applying the modified algorithm, EBQRMM. Table 6 also presents a comparison between EBQRMPM, dark cells, and EBQRMM algorithms, light cells.

Table 6.

A comparison between EBQRMPM and EBQRMM to show the effect of changing priority on the final path decision

Table 7.

Priority normalised weights (no prioritisation: EBQRMM algorithm)

Priority no#	1	2	3	4	∑
anprpcm	0.25	0.25	0.25	0.25	1

Table 8.

Final path decision applying EBQRMM algorithm (no prioritisation)

Total normalised path score							Selected path
P1	P2	P3	P4	P5	P6	P7
0.1601	0.118	0.162	0.093	0.178	0.140	0.146	5

3. Simulation and experimental design

In this section, simulation results are discussed and analysed. it is worth mentioning that some modifications and assumptions are added compared to what have been discussed in Section 2; security metric is considered as a range [0,1] rather than binary (0 or 1) and it is found that it would better to concentrate on vulnerability rather than security. More details are provided in Section 3.2.3.

3.1. Network model

To ensure that simulation of the different routing algorithms are independent of the topology of any specific networks, random graphs are used to model the communication networks studied applying Doar's model [24]. This model was proposed in 1993 as a modified version of Waxman's model, which was proposed in 1988 [25].

This model randomly distributes nodes over a rectangular coordinate grid. Edges are introduced with a probability that depends on their length. The edge probability is given by the following equation [24]:

(9)

where d(u,v) is the distance from node u to v, L is the maximum distance between two nodes, and α and β are parameters in the range (0,1). Small values of α increase the density of short edges relative to longer edges, while larger values of β produce higher node degrees. Edge lengths are selected at random from the range (1..L). e is the desired average degree, k is a scaling factor and size is the number of nodes [24].

This model, random graph generator, has been used in some research works. For example, [24], [25], [26], [27], [28], [29], [30], [31], [32], [33], [34] and [35].

For our simulation, these parameters are adjusted to some values, as shown in Table 9, in order to give a network with average degree around 4, which is reasonable for practical networks [26].

Table 9.

Summary of parameters and assumptions of the studied networks

Parameter	Information	Comments
Network size	15 nodes
Link type	OC3 (155 Mbps),	Fibre optic cable
Propagation delay factor
Queuing delay	S/(1-util)	2.735e-6* link_cap/re_bwa
Link residual bandwidth	Normal distribution (mean, SD)b	Mean=(1-util)*link capacity
		SD=0.8*mean
Link degree of security (DS)	uniform random distribution	[0–1]
Link degree of vulnerability (DV)	1-DS
Loss probability	uniform random distribution	[1e-8 to 1e-5]
Grid size		==Europe
Number of requests for each	1000
generated random network
Waxman parameters: Doar's model	Alpha=beta=0.2, k=20, e=4

^a Average service for 1 ATM cell. To use M/M/1 approximation.
^b If resbw>155→resbw=155-(resbw-155), if resbw<=0→resbw=1e-3+(0-resbw). Why? A- To deal with resbw outside the range (0–155) as a result of applying normal distribution and B- 1e-3 (1 kbps) has been added to avoid division by zero in queuing delay.

The nodes are placed in a , rectangular grid, roughly the area of Europe, using uniform distribution. Each link is bidirectional with a bandwidth capacity of 155 Mbps (OC3).

3.2. Link metrics

In this subsection, we will discuss our assumptions for the studied metrics. Namely, delay, bandwidth, security and loss probability.

3.2.1. Delay

Two types of delay have been considered; propagation and queuing delay. For propagation delay, nodes are assumed to be connected by fibre optic cables, which have a propagation delay of [36]. For queuing delay, it is assumed that an M/M/1 queuing model gives a good approximation that reflects queuing delay behaviour in the models of communication networks [37] and [38] which increases exponentially when utilisation (U) is high as depicted in Fig. 2. It is also assumed that average service time equals to the time required to process one ATM cell, 53 octets, see Table 9. It is worth emphasising that we apply M/M/1 as a very basic approximation since our focus is on QoS routing rather than modelling of queuing delay.

Fig. 2. An illustration of queuing delay behaviour vs. utilisation (U).

3.2.2. Residual bandwidth

The residual bandwidth for each link was assigned using normal distribution. One reason behind that is that normal distribution enables utilisation to be controlled by controlling values of the mean and standard deviation (SD). This can be achieved by controlling values of the mean and SD as depicted in Fig. 3. As can be seen from the figure, assigned bandwidth is more concentrated around the mean as SD decreases.

Fig. 3. An illustration of how SD affects probability of assigned bandwidth.

However, we faced the problem of a generated bandwidth being less than zero or greater than the maximum link capacity (155 Mbps in our model). We solved this problem by using the symmetric property of normal distribution. Therefore, we substitute the value outside the range (0–155) by the corresponding value from the second half of the distribution [38] and [39]. The following algorithm, Fig. 4, shows the implementation of this solution.

Fig. 4. The suggested algorithm to assign res_bw to a link applying the symmetric property of normal distribution.

3.2.3. Security

Although security is a very important and a hot topic in communication networks, it has not been defined, to the best of our knowledge, as a quantitative metric in order to be considered by QoS routing algorithms. Moreover, it is difficult to determine which composition rule will be applicable for security, e.g. concave or multiplicative metric? However, some proposed routing protocols have tried to include security as a QoS metric, e.g. [40] and [12]. The key idea there was to consider security in a binary form [41] and [42]. If a link has any level of security, the link will be assigned a value of 1, secured link. On the other hand, if it does not have any level of security, it will be assigned a value of 0, unsecured link.

In our simulations, a link is assigned a value randomly according uniform distribution on the range [0,1]. The actual mechanism of choosing the value of the security metric is outside the scope of this paper. The generated value is called the Degree of Security, DS. The aim is to minimise the number of unsecured links rather than to maximise number of secured links. This approach is more appropriate to reflect the vulnerability level of paths [38], [39] and [43]. Therefore, we defined a parameter called Degree of Vulnerability, DV. Hence, we assume that the unit of DV is (links) [38] and [39]. Based on this, DV for a link is given by:

DVl=1-DSl

(10)

Therefore, total DV of a path is given by:

DVp=∑(1-DSl)(links)

(11)

For example, a path of 5 links with (1, 0.5, 0.8, 0, 0.1) DS, will be considered as a path with DV=0+0.5+0.2+1+0.9=2.6 links. In other word, this path will be considered as a path that has 2.6 unsecured links. Therefore, security is treated as an additive metric like delay, delay jitter or cost. It is worth mentioning that this way of considering security is relative and therefore more suitable for best effort rather than constrained routing.

3.2.4. Loss probability

Each link is assigned a loss probability in the range 1e-8 to 1e-5 using uniform random distribution.

Table 9 summarises the assumptions and the parameters which have been used in the networks studied.

3.3. Evaluation method

Utilisation is varied from 0 to 1 as a controlling parameter. For each value, 1000 connection requests are generated. For each connection request, a random network is generated, each link is assigned value of the four metrics: delay, residual bandwidth, Degree of security (DS) and loss probability and two nodes are randomly selected as source and destination. Ten priority sets have been tested. For each priority set, the proposed algorithm, EBQRMPM, is applied to find a path between the two selected nodes.

Some parameters of the selected paths, path-delay, path-residual bandwidth, path-Degree of vulnerability (DV) and path-loss probability, are recorded. Then, the averages of these parameters are compared in order to collect some performance measures that can help to study, analyse and compare performance of the proposed algorithm to the other algorithms. In total, 11,000 random networks are generated. Fig. 5 shows the general flow of the simulation.

Fig. 5. The general flow of the simulation.

Five performance measures are used: average delay, average residual bandwidth, average Degree of Vulnerability (DV), average loss probability and percentage Improvement.

Percentage improvement in a metric m when changing priority from 0 to 1 is given by Eq. (5). Where, m₀ and m₁ are the values of a metric m when its priority is zero and one, respectively.

(12)

4. Performance evaluations and results analysis

In this section, performance of the proposed algorithm, EBQRMPM, when changing metrics priorities will be evaluated.

The priority sets are organised as shown in Table 10. Since there are four metrics and weights of priorities can be given any value on the range [0,1], it is expected to have large number of iterations and large number of possibilities to show results in curves. Therefore, we decided to select curves that show the best (priority=1), worst (priority=0), cases-A&D: sets-1, 8, 9 and 10, and equal priorities (0.25), case-C: set-7. The reason for selecting set-7 form case-C is that set-7 is a special case of priority sets in which all metrics have the same priority. This case is equivalent to the first version of the proposed algorithm where there was no prioritisation, EBQRMM [23] and [44].

Table 10.

Summary of priority organisation

Case	Priority set#	Comments	Priority weights				∑
			Del	bw	sec	loss
A	1	One metric is important only.	1	0	0	0	1
	2	(delay) is first important+1 other metric (bw)	0.7	0.2	0.05	0.05	1
B	3	(delay) is first important+2 other metric (bw, sec)	0.7	0.125	0.125	0.05	1
	4	(delay) is first important+3 other metric (bw, sec, loss)	0.7	0.1	0.1	0.1	1
	5	2 metrics are equally important (del, bw)	0.45	0.45	0.05	0.05	1
C	6	3 metrics are equally important (del, bw, sec)	0.32	0.32	0.32	0.04	1
	7	4 metrics are equally important (all)	0.25	0.25	0.25	0.25	1
	8	(delay has 0 importance && bw is 1)	0	1	0	0	1
D	9	(delay has 0 importance && sec is 1)	0	0	1	0	1
	10	(delay has 0 importance && loss is 1)	0	0	0	1	1

For each priority set, the four metrics, average delay, average residual bandwidth, average number of unsecured links and average loss probability, will be investigated. Then, the percentage improvement, Eq. (4), for each metric will be measured.

4.1. Effect of changing priorities

In this subsection, we will illustrate the effect of changing priorities on the performance of the proposed algorithm, EBQRMPM for each metric.

In general, it is found that changing priority of a metric from 0 to 1 improves the value of that metric by (20–60)%.

Table 11 shows the maximum achieved improvement on each metric. As can be seen from the table, maximum improvement on any metric is achieved when the priority of this metric is one while the priorities of the other metrics are zeros. Moreover, the collected results shown in the table, shows that priority sets that give maximum improvements for delay, bandwidth, and degree of vulnerability and loss probability are set-1, -8, -9, and -10, respectively.

Table 11.

Maximum acheived % improvement relative to the zero priority case

Metric	Delay	Bandwidth (bw)	Degree of vulnerability (DV)	Loss probability
Maximum % improvement	88.8	70.6	57.5	55.6
Priority set#	Set-1	Set-8	Set-9 and set-10	Set-10

4.1.1. Effect of changing priorities for delay

Fig. 6 shows average delay vs. mean link utilisation when changing its priority from 0 to 1. Each point on the curves is the average of 1000 values. Fig. 7 shows the percentage improvement in delay relative to the worst case, when it has zero priority (set-9).

Fig. 6. Average delay vs. mean link utilisation for different priority sets. Each point on the curves is the average of 1000 values.

Fig. 7. Percentage improvement in delay relative to zero priority (set-9).

As can be seen from the figures, increasing delay priority improves the delay metrics of the selected path. It is found that on the average the delay produced by EBQRMPM-set1 is lower (better) than EBQRMPM-set9 by (21–25)%, with average of 22% and 1.4% SD, for utilisation from 0 to 0.9. This improvement rises to 88% at utilisation of 1.

4.1.2. Effect of changing priorities for bandwidth

Fig. 8 shows average bandwidth vs. mean link utilisation when changing its priority from 0 to 1. Each point on the curves is the average of 1000 values. Fig. 9 shows the percentage improvement in bandwidth relative to the worst case, when it has zero priority (set-9).

Fig. 8. Average bandwidth vs. mean link utilisation when changing its priority from 0 to 1. Each point on the curves is the average of 1000 values.

Fig. 9. Percentage improvement in bandwidth relative to zero priority (set-9).

As can be seen from the figures, increasing bandwidth priority improves the bandwidth metrics of the selected path. It is found that on the average the bandwidth produced by EBQRMPM-set8 is higher (better) than EBQRMPM-(set9 and set10) by (50–70)%, with average of 60% and 5% SD, for utilisation from 0 to 0.9. This improvement decreases to 0% at utilisation of 1. This is because at very high level of utilisation, it is expected that paths selected by different priority sets will have very similar bandwidths, assuming that the networks have symmetric load.

4.1.3. Effect of changing priorities for vulnerability

Fig. 10 shows average degree of vulnerability vs. mean link utilisation when changing its priority from 0 to 1. Each point on the curves is the average of 1000 values. Fig. 11 shows the percentage improvement in degree of vulnerability relative to the worst case, when it has zero priority (set-8).

Fig. 10. Average degree of vulnerability when changing its priority from 0 to 1. Each point on the curves is the average of 1000 values.

Fig. 11. Percentage improvement in degree of vulnerability relative to zero priority (set-8).

As can be seen from the figures, increasing degree of vulnerability priority improves the degree of vulnerability metrics of the selected path. It is found that on the average the degree of vulnerability produced by EBQRMPM-set9 is lower (better) than EBQRMPM-set8 by an average of 57% and 1.7% SD, for the whole range of utilisation.

4.1.4. Effect of changing priorities for loss probability

Fig. 12 shows average loss probability vs. mean link utilisation when changing its priority from 0 to 1. Each point on the curves is the average of 1000 values. Fig. 13 shows the percentage improvement in degree of vulnerability relative to the worst case, when it has zero priority (set-8).

Fig. 12. Average loss probability vs. mean link utilisation when changing its priority from 0 to 1. Each point on the curves is the average of 1000 values.

Fig. 13. Percentage improvement in loss probability relative to zero priority (set-8).

As can be seen from the figures, increasing loss probability priority improves the loss probability metrics of the selected path. It is found that on the average the loss probability produced by EBQRMPM-set10 is lower (better) than EBQRMPM-set8 by an average of 53% and 1.5% SD, for the whole range of utilisation.

5. Limitations of EBQRMPM

Despite the overall promising performance of the proposed algorithm (EBQRMPM) in best effort QoS routing with multiple and prioritised metrics, it has been found that there is a complexity drawback. After investigation, it is found that its complexity is caused by: firstly, the step of finding all possible paths (P) between src and ter. Secondly, the steps of constructing the , and matrices.

However, since this proposal of applying AHP at QoS routing is new and it has not been proposed previously, we are still optimistic that there are possibilities to investigate this complexity problem in more detail in order for it to be minimised. One promising observation is that the columns of the matrix, Step-C, are identical. Therefore, it would be enough to construct and instead of (P,P), thus, the step of constructing can be deleted.

6. Conclusions and future work

In this paper, firstly, a new approach that applies the concept of the Analytic Hierarchy Process (AHP) in the area of routing in communication networks has been proposed. AHP is a well-known model in the area of decision making with multiple objectives. Secondly, a new algorithm called Enhanced Best Effort Quality of Service Routing (QoS) with Multiple Prioritised Metrics (EBQRMPM) has also been proposed. It is proposed for connection-oriented point-to-point communications. Four metrics have been considered: delay, bandwidth, security and loss probability. Thirdly, more detailed results were discussed and analysed especially in order to show effects of metric prioritisation. Simulation experiments demonstrated that the AHP method enables the improvement in a metric to be quantified in terms of its prioritisation. It has been found that changing priority of a metric from 0 to 1 applying the proposed algorithm improves the value of that metric by an average of (20–60)% for 90% of utilisation range.

For future work, the proposed algorithm, EBQRMPM, will be compared to some other routing algorithms in order to investigate it performance in more detail. Firstly, it will be compared to the EBQRMM algorithm [44] (Section 2.2). Secondly, it will be compared to Dijkstra shortest path and some other related algorithms. More work has to be done in order to minimise its complexity drawback. Since EBQRMPM is proposed for connection-oriented networks, it can be modified to support connection-less oriented network like Internet. It seems that this direction will contribute to minimise the complexity drawback since Step-A will turn to find all possible outgoing links from a specified node rather than finding all possible paths between source and destination nodes.

References

[1] M. Furini and D.F. Towsley, Real-time traffic transmissions over the internet, IEEE Transactions on Multimedia 3 (2001), pp. 33–40. Abstract-INSPEC | Abstract-Compendex   | $Order Document | Full Text via CrossRef

[2] A. Dubrovsky, M. Gerla, S.S. Lee and D. Cavendish, Internet QoS routing with IP telephony and TCP traffic, Proceedings of IEEE International Conference in Communications (ICC 2000) (2000), pp. 1348–1352. Abstract-Compendex   | $Order Document | Full Text via CrossRef

[3] X.P. Xiao and L.M. Ni, Internet QoS A big picture, IEEE Networks 13 (1999), pp. 8–18. Abstract-Compendex   | $Order Document

[4] G. Lu, Issues and technologies for supporting multimedia communications over the Internet, Computer Communications 23 (2000), pp. 1323–1335. SummaryPlus | Full Text + Links | PDF (118 K)

[5] IETF: L. Zhang, S. Berson, S. Herzog, S. Jamin, Resource ReSerVation Protocol (RSVP). September 1997, http://www.sciencedirect.com/science?_ob=RedirectURL&_method=externObjLink&_locator=url&_cdi=5945&_plusSign=%2B&_targetURL=http%253A%252F%252Fcommunity.roxen.com%252Fdevelopers%252Fidocs%252Frfc%252Frfc2205.html.

[6] IETF: R. Braden, D. Clark, S. Shenker, Integrated services in the internet architecture: an overview. June 1994, http://www.sciencedirect.com/science?_ob=RedirectURL&_method=externObjLink&_locator=url&_cdi=5945&_plusSign=%2B&_targetURL=http%253A%252F%252Fcommunity.roxen.com%252Fdevelopers%252Fidocs%252Frfc%252Frfc1633.html.

[7] IETF: S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, W. Weiss, An architecture for differentiated services. December 1998, http://www.sciencedirect.com/science?_ob=RedirectURL&_method=externObjLink&_locator=url&_cdi=5945&_plusSign=%2B&_targetURL=http%253A%252F%252Fcommunity.roxen.com%252Fdevelopers%252Fidocs%252Frfc%252Frfc2475.html.

[8] IETF: E. Rosen, A. Viswanathan, R. Callon, Multiprotocol Label Switching Architecture (MPLS). 2001, http://www.sciencedirect.com/science?_ob=RedirectURL&_method=externObjLink&_locator=url&_cdi=5945&_plusSign=%2B&_targetURL=http%253A%252F%252Fcommunity.roxen.com%252Fdevelopers%252Fidocs%252Frfc%252Frfc3031.html.

[9] IETF: E. Crawley, R. Nair, et al. A framework for QoS- based routing in the internet. August 1998, http://www.sciencedirect.com/science?_ob=RedirectURL&_method=externObjLink&_locator=url&_cdi=5945&_plusSign=%2B&_targetURL=http%253A%252F%252Fcommunity.roxen.com%252Fdevelopers%252Fidocs%252Frfc%252Frfc2386.html.

[10] B.G. Kim, The Soft QoS Service (SQS) in the Internet, Proceedings of Fourth IEEE International Conference on ATM (ICATM 2001) (April 2001), pp. 56–60.

[11] Z. Wang and J. Crowcroft, Quality-of-service routing for supporting multimedia applications, IEEE Journal on Selected Areas in Communications 14 (1996), pp. 1228–1234. Abstract-Compendex   | $Order Document

[12] A.M.S. Alkahtani, M.E. Woodward, K. Al-Begain and A. Alghannam, QoS routing with multiple and prioritised constraints using the concept of the analytic hierarchy process (AHP), Proceedings of International Network Conference INC2002, UK (2002), pp. 243–251.

[13] M. Kanbara, H. Tanioka, K. Kinoshita and K. Murakami, A multicast routing algorithm for multiple QoS requirements, Proceedings of International Network Conference INC2002, Plymouth, UK (2002), pp. 253–260.

[14] T.L. Saaty, The analytic hierarchy process, McGraw Hill, New York (1980).

[15] W.L. Winston, Operations research applications and algorithms (3rd ed.), International Thomson Publishing (1994).

[16] P. Klungboonkrong and M.A.P. Taylor, A microcomputer-based- system for multicriteria environmental impacts evaluation of urban road networks, Computers, Environment and Urban Systems 22 (1998), pp. 425–446. Abstract | Full Text + Links | PDF (1862 K)

[17] P.K. Dey and S.S. Gupta, Decision-support system yields better pipeline route, Oil and Gas Journal 98 (2000), pp. 68–73. Abstract-FLUIDEX   | $Order Document

[18] N.-P. Wang, The application of analytic hierarchy process in the selection of hospital, Chinese Journal of Public Health 18 (1999), pp. 138–151. Abstract-EMBASE   | $Order Document

[19] K.M.A.-S. Al-Harbi, Application of the AHP in project management, International Journal of Project Management 19 (2001), pp. 19–27. SummaryPlus | Full Text + Links | PDF (191 K)

[20] N. Sato and H. Kataoka, Selecting network services based on joint assessment by customer and provider, Proceedings of IEEE GLOBECOM’96 Conference (1996), pp. 634–638. Abstract-Compendex   | $Order Document | Full Text via CrossRef

[21] A.A. Andijani, Buffer management of a switch for ATM networks a multi-objective approach, Computer Systems Science and Engineering 13 (1998), pp. 379–386. Abstract-INSPEC | Abstract-Compendex   | $Order Document

[22] C. Douligeris and I.J. Pereira, A telecommunications quality study using the analytical hierarchy process, IEEE Journal on Selected Areas in Communications 12 (1994), pp. 241–250. Abstract-Compendex | Abstract-INSPEC   | $Order Document | Full Text via CrossRef

[23] A.M.S. Alkahtani, M.E. Woodward, K. Al-Begain and A. Alghannam, Enhanced best effort QoS routing with multiple and prioritised metrics using the analytic hierarchy process (AHP) concept, Proceedings of International Conference on Automation and Information ICAI02, Spain (2002).

[24] Doar JM. Multicast in the asynchronous transfer mode environment. PhD. St. John's College, University of Cambridge, London; January 1993.

[25] B.M. Waxman, Routing of multipoint connections, IEEE Journal on Selected Areas in Communications 6 (1988), pp. 1617–1622. Abstract-Compendex | Abstract-INSPEC   | $Order Document | Full Text via CrossRef

[26] H.F. Salama, D.S. Reeves and Y. Viniotis, Evaluation of multicast routing algorithms for real-time communication on high-speed networks, IEEE Journal On Selected Areas in Communications 15 (1997), pp. 332–345. Abstract-INSPEC | Abstract-Compendex   | $Order Document | Full Text via CrossRef

[27] T. Alrabiah and T.F. Znati, An efficient and easily deployable QoS-based routing scheme for online Internet multicasting, Computer Communications 24 (2001), pp. 496–511. SummaryPlus | Full Text + Links | PDF (424 K)

[28] L. Layuan and L. Chunling, QoS-based routing algorithms for ATM networks, Computer Communications 24 (2001), pp. 416–421. SummaryPlus | Full Text + Links | PDF (217 K)

[29] J.J. Wu, R.H. Hwang and H.I. Lu, Multicast routing with multiple QoS constraints in ATM networks, Information Sciences 124 (2000), pp. 29–57. SummaryPlus | Full Text + Links | PDF (877 K)

[30] D.S. Reeves and H.F. Salama, A distributed algorithm for delay-constrained unicast routing, IEEE-ACM Transactions On Networking 8 (2000), pp. 239–250. Abstract-INSPEC   | $Order Document | Full Text via CrossRef

[31] Alrabiah TF. Multicast routing in wide-area high speed networks. PhD. University Pittsburgh, Pittsburgh; 1999.

[32] Crawford JS. A hybrid approach to quality of service multicast routing in high speed networks. PhD. University of Kent at Canterbury, 1998.

[33] H.D. Neve and P.V. Mieghem, A multiple quality of service routing algorithm for PNNI, Proceedings of IEEE Workshop 1998 (1998), pp. 324–328.

[34] H.F. Salama, D.S. Reeves and Y. Viniotis, A distributed algorithm for delay-constrained unicast routing, Proceedings of IEEE INFOCOM97 Japan (1997), pp. 84–91. Abstract-Compendex   | $Order Document | Full Text via CrossRef

[35] D.-W. Shin, E.K.P. Chong and H.J. Seigel, A multiconstrait QoS routing scheme using the depth-first search method with limited crankback, Proceedings of Workshop on High Performance Switching and Routing Dallas, TX, USA (2001), pp. 385–389. Abstract-Compendex   | $Order Document

[36] R.O. Onvural, Asynchronous transfer mode networks performance issues (2nd ed.), Boston, Artech House (1995).

[37] J.M. Pitts and J.A. Schormans, Intoduction to IP/ATM design and performance, Wiley, New York (2000).

[38] Woodward ME. Department of Computing, University of Bradford, Personal communication, 3/5/2002.

[39] Al-Begain K. Department of Computing, University of Bradford, Personal communication, 10/4/2002.

[40] M.M.M. Al-Fawaz and M.E. Woodward, Fast quality of service routing algorithms with multiple constraints, Proceedings of Eighth IFIP Workshop on ATM&IP Ilkely, UK (July 2000), pp. 01/1–01/10.

[41] M. Baltatu, A. Lioy, F. Maino and D. Mazzocchi, Security issues in control, management and routing protocols, Computer Networks-the International Journal of Computer and Telecommunications Networking 34 (2000), pp. 881–894. SummaryPlus | Full Text + Links | PDF (199 K)

[42] B.R. Smith and J.J. Garcia-Luna-Aceves, Efficient security mechanisms for the border gateway routing protocol, Computer Communications 21 (1998), pp. 203–210. Abstract | Full Text + Links | PDF (1089 K)

[43] Furnell S. Network research group, Department of Communication & EE, University of Plymouth, sfunell@plymouth.ac.uk, http://www.sciencedirect.com/science?_ob=RedirectURL&_method=externObjLink&_locator=url&_cdi=5945&_plusSign=%2B&_targetURL=http%253A%252F%252Fted.see.plym.ac.uk%252Fnrg, Personal Communication, 18/7/2002.

[44] A.M.S. Alkahtani, M.E. Woodward and K. Al-Begain, Enhanced best effort QoS routing with multiple metrics (EBQRMM), Saudi Computer Journal Appliedm Computing & Informatics 2 (2004) (2), pp. 27–41 ISSN 1319-5107.

Corresponding author. Tel.: 0044-1274-233921; fax: 0044-1274-233920.